/**
 * @file IntervalTree.h
 * @brief 
 * @author lichen 
 * @version 1.0
 * @date 2020-12-29
 * @copyright Copyright (c) 2020  
 */
#include"RedBlackTree.h"//在BST目录下//
template<class T>
class IntervalTree
{
 public:
  typedef typename RedBlackTree<T>::Node Node;
  IntervalTree(T _low, T _high): RedBlackTree<T>(_low, _high)
    {
      this->root->color = BLACK;
    };
  IntervalTree(){};
  ~IntervalTree(){};
  Node *IntervalSearch(Node* i);
  Node *IntervalSearch(T _low, T _high);
};

template <class T>
typename IntervalTree<T>::Node *IntervalTree<T>::IntervalSearch(Node* i)
{ 
  Node* x = this->root;
  x->lc->max = this->max(x->lc);
  while(x!=this->nil && (i->low->data >= x->high->data || x->low->data > i->high->data) )
    {
      if(x->lc != this->nil && i->low->data <= x->lc->max->data)
	{
	  x=x->lc;
	  x->lc->max = this->max(x->lc);
	}
      else
	{
	  x=x->rc;
	  x->lc->max = this->max(x->lc);
	}
    }
  return x;
}

template <class T>
typename IntervalTree<T>::Node *IntervalTree<T>::IntervalSearch(T _low, T _high)
{
  Node* t = new Node;
  t->low = new Node;
  t->high = new Node;
  t->low->data = _low;
  t->high->data = _high;
  t->lc=t->rc= this->nil;
  return IntervalSearch(t);

}

